১. N-Queens Problem
বর্ণনা
N-Queens Problem একটি ক্লাসিক্যাল সমস্যা যেখানে N × N এর একটি শাসনের (chessboard) উপর N টি রানীকে (queens) এমনভাবে স্থাপন করতে হয় যে কোন দুটি রানী একে অপরকে আক্রমণ করতে না পারে। অর্থাৎ, কোনও দুটি রানী একই সারি, কলাম বা ডায়াগনালে থাকতে পারবে না।
উদাহরণ
- N = 4
- একটি সম্ভাব্য সমাধান:
. Q . .
. . . Q
Q . . .
. . Q .
ব্যাকট্র্যাকিং পদ্ধতি ব্যবহার করে সমাধান
def print_solution(board):
for row in board:
print(" ".join(row))
print("\n")
def is_safe(board, row, col):
# একই কলামে পরীক্ষা
for i in range(row):
if board[i][col] == 'Q':
return False
# ডায়াগনালে পরীক্ষা
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 'Q':
return False
for i, j in zip(range(row, -1, -1), range(col, len(board))):
if board[i][j] == 'Q':
return False
return True
def solve_n_queens_util(board, row):
if row >= len(board):
print_solution(board)
return True
for col in range(len(board)):
if is_safe(board, row, col):
board[row][col] = 'Q' # রানী স্থাপন
solve_n_queens_util(board, row + 1) # পরবর্তী সারিতে যান
board[row][col] = '.' # ব্যাকট্র্যাকিং
def solve_n_queens(n):
board = [['.' for _ in range(n)] for _ in range(n)]
solve_n_queens_util(board, 0)
# N-Queens সমস্যা সমাধান করা
solve_n_queens(4)
২. Sudoku Solver
বর্ণনা
Sudoku হল একটি সংখ্যা ভিত্তিক পাজল যা একটি 9 × 9 গ্রিডে খেলা হয়। এই গ্রিডে 1 থেকে 9 পর্যন্ত সংখ্যা স্থাপন করতে হবে, যাতে প্রতিটি সারি, কলাম এবং 3 × 3 এর সাবগ্রিডে একই সংখ্যা দুইবার না থাকে।
উদাহরণ
5 3 . | . 7 . | . . .
6 . . | 1 9 5 | . . .
. 9 8 | . . . | . 6 .
---------------------
8 . . | . 6 . | . . 3
4 . . | 8 . 3 | . . 1
7 . . | . 2 . | . . 6
---------------------
. 6 . | . . . | 2 8 .
. . . | 4 1 9 | . . 5
. . . | . 8 . | . 7 9
ব্যাকট্র্যাকিং পদ্ধতি ব্যবহার করে সমাধান
def print_board(board):
for row in board:
print(" ".join(str(num) for num in row))
print("\n")
def find_empty_location(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0: # শূন্য স্থান খুঁজে পাওয়া
return (i, j)
return None
def is_safe(board, row, col, num):
# সারিতে পরীক্ষা
if num in board[row]:
return False
# কলামে পরীক্ষা
for r in range(9):
if board[r][col] == num:
return False
# 3x3 সাবগ্রিডে পরীক্ষা
start_row = row - row % 3
start_col = col - col % 3
for i in range(3):
for j in range(3):
if board[i + start_row][j + start_col] == num:
return False
return True
def solve_sudoku(board):
empty = find_empty_location(board)
if not empty:
return True # Sudoku সমাধান হয়েছে
row, col = empty
for num in range(1, 10): # 1 থেকে 9 পর্যন্ত পরীক্ষা
if is_safe(board, row, col, num):
board[row][col] = num # সংখ্যা স্থাপন
if solve_sudoku(board): # পুনরায় সমাধান করার চেষ্টা
return True
board[row][col] = 0 # ব্যাকট্র্যাকিং
return False
# Sudoku সমাধান উদাহরণ
sudoku_board = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
]
if solve_sudoku(sudoku_board):
print("Sudoku solved:")
print_board(sudoku_board)
else:
print("No solution exists")
উপসংহার
N-Queens Problem এবং Sudoku Solver উভয়ই ব্যাকট্র্যাকিং পদ্ধতি ব্যবহার করে সমাধান করা যায়। N-Queens Problem নির্দিষ্ট অবস্থানে রানী রাখার একটি অপ্টিমাইজেশন সমস্যা, যেখানে Sudoku একটি সংখ্যার পাজল যা সঠিকভাবে পূর্ণ করার জন্য নির্দিষ্ট নিয়ম অনুসরণ করতে হয়। উভয় সমস্যা বিভিন্ন অ্যালগরিদমিক কৌশল ব্যবহার করে, যা তাদের সমাধানে কার্যকর।
